package pers.qianyu.month_202101.date_20210114;

import java.util.*;

/**
 * 706. 设计哈希映射
 * https://leetcode-cn.com/problems/design-hashmap/
 * - 开放寻址法实现
 *
 * @author mizzle rain
 * @date 2021年1月14日17:28:48
 */
public class MyHashMap2 {
    private static final int N = 20011;
    private int[] keyTable;
    private int[] valueTable;


    public MyHashMap2() {
        keyTable = new int[N];
        Arrays.fill(keyTable, -1);
        valueTable = new int[N];
    }

    public void put(int key, int value) {
        int hash = hash(key);
        if (keyTable[hash] == -1 || keyTable[hash] == -2) {
            keyTable[hash] = key;
            valueTable[hash] = value;
        } else {
            for (int i = hash; i < N; i = (i + 1) % N) {
                if (keyTable[i] == key || keyTable[i] == -1) {
                    keyTable[i] = key;
                    valueTable[i] = value;
                    return;
                }
            }
        }
    }

    public int get(int key) {
        int hash = hash(key);
        if (keyTable[hash] == -1) {
            return -1;
        } else if (keyTable[hash] == key) {
            return valueTable[hash];
        } else {
            for (int i = hash + 1; i != hash; i = (i + 1) % N) {
                if (keyTable[i] == key) {
                    return valueTable[i];
                }
            }
        }
        return -1;
    }

    public void remove(int key) {
        int hash = hash(key);
        if (keyTable[hash] == key) {
            keyTable[hash] = -2;
            return;
        }
        for (int i = hash + 1; i != hash; i = (i + 1) % N) {
            if (keyTable[i] == key) {
                keyTable[i] = -2;
                return;
            }
        }
    }

    private int hash(int key) {
        return key % N;
    }

    public static void main(String[] args) {
        MyHashMap2 map = new MyHashMap2();
        map.put(1, 1);
        map.put(2, 2);
        System.out.println(map.get(1));
        System.out.println(map.get(3));
        map.put(2, 1);
        System.out.println(map.get(2));
        map.remove(2);
        System.out.println(map.get(2));
    }
}
